import java.util.Arrays;

/**
 * 归并排序（Merge Sort）
 * 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
 * 核心思想是将数组递归地分成两半，分别排序后再合并有序子数组。
 * 算法步骤：
 * 1.分解：将数组分成两个子数组，直到每个子数组只有一个元素（天然有序）。
 * 2.合并：将两个有序子数组合并为一个有序数组。
 * 空间复杂度：由于需要辅助空间，所以复杂度为O(n)
 * 时间复杂度：每次归并的时间复杂度为O(n)，需要进行log(n)次归并，所以时间复杂度为O(n log n)
 *
 * @author Liu Yicong
 * @date 2025/9/21
 */
public class MergeSort {
	/**
	 * 对整个数组执行归并排序的入口方法。
	 *
	 * @param arr 待排序的整数数组。
	 */
	public static void sort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		// 1. 创建辅助数组，与原数组大小相同
		int[] temp = new int[arr.length];
		// 2. 调用递归排序方法
		mergeSort(arr, temp, 0, arr.length - 1);
	}

	/**
	 * 递归执行归并排序的主要方法（分）。
	 *
	 * @param arr   原始数组。
	 * @param temp  辅助数组。
	 * @param left  归并段的起始索引。
	 * @param right 归并段的结束索引。
	 */
	private static void mergeSort(int[] arr, int[] temp, int left, int right) {
		// 递归终止条件：当子数组只有一个元素时（left >= right）
		if (left < right) {
			// 找到中间点，执行分解
			int mid = left + (right - left) / 2;

			// 递归地排序左半部分
			mergeSort(arr, temp, left, mid);

			// 递归地排序右半部分
			mergeSort(arr, temp, mid + 1, right);

			// 合并左右两个有序子数组
			merge(arr, temp, left, mid, right);
		}
	}

	/**
	 * 合并两个有序子数组的方法（治）。
	 * 将 arr[left...mid] 和 arr[mid+1...right] 合并。
	 *
	 * @param arr   原始数组。
	 * @param temp  辅助数组。
	 * @param left  左子数组的起始索引。
	 * @param mid   左子数组的结束索引。
	 * @param right 右子数组的结束索引。
	 */
	private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
		// 1. 将待合并的数据复制到辅助数组 temp 中
		// 只需要复制当前要处理的段 [left, right]
		for (int i = left; i <= right; i++) {
			temp[i] = arr[i];
		}

		// 2. 初始化指针
		int i = left;      // 左子数组的起始指针 (temp)
		int j = mid + 1;   // 右子数组的起始指针 (temp)
		int k = left;      // 目标数组（arr）的填充指针

		// 3. 比较并合并：将较小的元素放回 arr 数组
		while (i <= mid && j <= right) {
			// 使用 <= 确保了归并排序的稳定性
			if (temp[i] <= temp[j]) {
				arr[k] = temp[i];
				i++;
			} else {
				arr[k] = temp[j];
				j++;
			}
			k++;
		}

		// 4. 处理左边剩余元素
		// 如果左子数组还有剩余，直接复制到 arr 的末尾
		while (i <= mid) {
			arr[k] = temp[i];
			k++;
			i++;
		}

		// 5. （可选）处理右边剩余元素。通常可以省略，因为如果右子数组有剩余，
		// 它们已经在 temp[j...right] 中，且位置就是 k 之后，它们本就应该在 arr 中 k 之后的位置。
	}

	// --- 测试代码 ---
	public static void main(String[] args) {
		int[] data = {12, 11, 13, 5, 6, 7};
		System.out.println("原始数组: " + Arrays.toString(data));

		MergeSort.sort(data);

		System.out.println("排序结果: " + Arrays.toString(data)); // 预期: [5, 6, 7, 11, 12, 13]

		int[] data2 = {5, 4, 3, 2, 1};
		MergeSort.sort(data2);
		System.out.println("反序数组排序结果: " + Arrays.toString(data2)); // 预期: [1, 2, 3, 4, 5]
	}

}
